
//过桥  贪心+BFS
int func(vector<int> v)
{
	int n = v.size();
	vector<int> dis(n + 1, INT_MAX);
	dis[1] = 0;   //dis[i]表示从起点1下标处到达i下标处，经过的秒数
	queue<int> q;
	q.push(1);
	while (!q.empty())
	{
		int tmp = q.front();
		q.pop();
		if (tmp == n)
		{
			return dis[n];
		}
		//根据题意分三种情况
		if (v[tmp] > 0)
		{
			for (int i = tmp + 1;i <= n && i <= v[tmp] + tmp;++i)
			{
				if (v[tmp] + 1 < v[i])
				{
					dis[i] = dis[tmp] + 1;
					q.push(i);
				}
			}
		}
		else if (v[tmp] < 0)
		{
			if (tmp + v[tmp] < 1)
			{
				if (dis[tmp] + 1 < dis[1])
				{
					dis[1] = dis[tmp] + 1;
					q.push(1);
				}
			}
			else
			{
				for (int i = 1;i <= tmp + v[tmp];++i)
				{
					if (dis[tmp] + 1 < dis[i])
					{
						dis[i] = dis[tmp] + 1;
						q.push(i);
					}
				}
			}
		}
	}
	return -1;
}


//时间复杂度26O(n)
int MinOperCount(std::string str)
{
	size_t minCount = INT_MAX;
	for (int i = 1;i <= 26;++i)
	{
		size_t tmp = 0;
		for (auto& e : str)
		{
			e -= 'a';
			e += 1;
			tmp += min(abs(i - e), (26 - (abs(i - e))));
		}
		minCount = min(minCount, tmp);
	}
	return minCount;
}


//求和

void dfs(int begin, int n,int m,int& sum,vector<int>& v,vector<vector<int>>& vv)
{
	if (begin > n)
	{
		return;
	}
	for (int i = begin;i <= n;++i)
	{
		if (sum > n)
		{
			break;
		}
		sum += i;
		v.push_back(i);
		if (sum == m)
		{
			vv.push_back(v);
			sum -= i;
			v.pop_back();
			break;
		}
		dfs(i + 1, n, m, sum, v, vv);
		sum -= i;
		v.pop_back();
	}
	return;
}



void Sum(int n, int m)
{
	vector<vector<int>> vv;
	vector<int> v;
	int sum = 0;
	dfs(1, n, m, sum, v, vv);
	return;
}

